﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace sudokuForm
{
    public class Sudoku
    {
        public int[,] Map = new int[9, 9];

        public void Init()
        { }

        public void Init(string mapstr)
        {

        }

        public bool GetResult()
        {
            while (true)
            {   // 先循环检查，将只有一个可能的值的填写上
                for (int i = 0; i < 9; i++)
                {
                    for (int j = 0; j < 9; j++)
                    {
                        List<int> rList = new List<int>();
                        rList.AddRange(WA(i));
                        rList.AddRange(HA(j));
                        rList.AddRange(LA(i, j));
                        rList = rList.Distinct().ToList();
                        if (rList.Count == 8)
                        {
                            for (int k = 1; k <= 9; k++)
                            {
                                if (!rList.Contains(k))
                                    Map[i, j] = k;
                            }
                        }
                        if (rList.Count == 9)
                            return false;
                    }
                }
                break;
            }

            if (Success())
                return true;

            while (true)
            {
                // 再循环检查，对于有多个值的可能，分别赋值，然后再检查
                for (int i = 0; i < 9; i++)
                {
                    for (int j = 0; j < 9; j++)
                    {
                        List<int> rList = new List<int>();
                        rList.AddRange(WA(i));
                        rList.AddRange(HA(j));
                        rList.AddRange(LA(i, j));
                        rList = rList.Distinct().ToList();
                        if (rList.Count < 8 )
                        {
                            for (int k = 1; k <= 9; k++)
                            {
                                var ns = this.Clone();
                                ns.Map[i, j] = k;
                                if (ns.GetResult())
                                {
                                    this.Map = ns.Map;
                                    return true;
                                }
                            }
                        }
                    }
                }
                break;
            }


            return false;
        }

        private Sudoku Clone()
        {
            var sdk = new Sudoku();

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    sdk.Map[i, j] = this.Map[i, j];
                }
            }
            return sdk;
        }

        private int[] WA(int j)
        {
            List<int> list = new List<int>();
            for (int i = 0; i < 9; i++)
            {
                if (Map[i, j] != 0)
                    list.Add(Map[i, 9]);
            }
            return list.ToArray();
        }

        private int[] HA(int i)
        {
            List<int> list = new List<int>();
            for (int j = 0; j < 9; i++)
            {
                if (Map[i, j] != 0)
                    list.Add(Map[i, j]);
            }
            return list.ToArray();
        }

        private int[] LA(int i, int j)
        {
            List<int> list = new List<int>();
            var si = i / 3;
            var sj = j / 3;
            for (int i1 = 0; i1 < 3; i1++)
            {
                for (int j1 = 0; j1 < 3; j1++)
                {
                    if (Map[si + i1, sj + j1] != 0)
                        list.Add(Map[si + i1, sj + j1]);
                }
            }
            return list.ToArray();
        }

        private bool Success()
        {
            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    if (Map[i, j] == 0)
                        return false;
                }
            }
            return true;
        }
    }
}
